package q1475_finalPrices;

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution {
    /*
    单调栈的典型例题 找每个元素右侧第一个小于等于它的元素
     */
    public int[] finalPrices(int[] prices) {
        Deque<Integer> stack = new ArrayDeque<>();
        int[] counts = new int[prices.length];
        for (int i = prices.length - 1; i >= 0; --i) {
            while (!stack.isEmpty() && prices[stack.peek()] > prices[i]) {
                stack.pop();
            }
            counts[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        for (int i = 0; i < prices.length; ++i) {
            prices[i] -= counts[i] == -1 ? 0 : prices[counts[i]];
        }
        return prices;
    }
}
